package com.yiguang.algorithm.dp;

import com.alibaba.fastjson.JSON;

/*
 * 200. 岛屿数量
 * 思路：从第一行第一列开始遍历，如果是1则将结果加1，并开始dfs遍历，如果是1则改其改为0
	给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
	岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
	此外，你可以假设该网格的四条边均被水包围。
	示例 1：
	
	输入：grid = [
	  ["1","1","1","1","0"],
	  ["1","1","0","1","0"],
	  ["1","1","0","0","0"],
	  ["0","0","0","0","0"]
	]
	输出：1
 */
public class IslandNum {
	
	public int getIslandNum(int[][] grid) {
		int result = 0;
		int rowLength = grid.length;
		int colLength = grid[0].length;
		for(int i=0; i<rowLength; i++) {
			for(int j=0; j<colLength; j++) {
				int current = grid[i][j];
				if(current==1) {
					result++;
					grid[i][j]=0;
					dfs(grid, i, j, rowLength, colLength);
				}
			}
		}
		return result;
	}
	
	public void dfs(int[][] grid, int row, int column, int rowLength, int colLength) {
		if(column+1<colLength && grid[row][column+1]==1) {
			grid[row][column+1]=0;
			dfs(grid, row, column+1, rowLength, colLength);
		}
		if(row+1<rowLength && grid[row+1][column]==1) {
			grid[row+1][column]=0;
			dfs(grid, row+1, column, rowLength, colLength);
		}
	}
	
	public static void main(String[] args) {
		/*
		 * 11000
		 * 11000
		 * 00100
		 * 00011
		 */
		int[][] grid = {{1,1,0,0,0},{1,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1}};
		IslandNum islandNumProblem = new IslandNum();
		System.out.println(islandNumProblem.getIslandNum(grid));
	}
}
